Project Phases and Scopes
Summary
This section lists motivations and scenarios of usage of G2K project. Then it defines the prject scopes, sizing estimates, and implementation phases.
G2K URLs:
Home page: https://g2kjalsethu.in/
Interactive Exploration: https://g2kjalsethu.in/g2k/index.html
Scenarios
Many major cities face frequent water scarcity. How to cost-effectively bring water from far away sources?
Many industrial concentrations pollute waterways. How to cost-effectively divert water from such regions?
Climatic changes are bringing extreme river flooding with severe economic consequences. How to link waterways to divert away the flood-waters?
By geographical nature of the subcontinent, India's north-east region is regularly flooded -- while the southern regions regularly face draught condition. How to remove both the conditions?
While canal transportation is the most efficienct method, India has not realized this potential. How could rivers be linked cost-effectively for such canals?
Scenario Explorations
S1: Kaveri river to Bengaluru
From: 76.7883, 12.3879 (south of Mandya) to 77.3536, 13.0865 (west of Neelamangala)
S2: Flood diversion from Prayagraj to Narmada river
presentation_flood_diversion_of_ganga_to_narmadha.png
River diversion of Sutlej river to Yamuna river
presentation_river_diversion_of_sutlej_to_yamuna.png
S3: Pollution Avoidance
From: 77.1572, 29.3075 (SE of Panipat) To: 77.7867, 27.3908 (south of Madura)
presentation_divert_yamuna_from_delhi.png
S4: Multi-faceted Project Planning
presentation_full_search_from_godhavari_to_krishna.png
S5: Parameter-based Project Planning
presentation_river_diversion_of_sutlej_to_yamuna.png
Canal across all east-west rivers
g2k_ganga_to_kaveri_route_05132025.png
Krishna river to Chennai
Phases
Phase0: India OSM For Land Polygons
PHASE1: Import DEM raster from Japan Space Systems
PHASE2: Convert GeoTiff files to Java binary files
PHASE3PRE: Prepare PostGreSQL
PHASE3: Cost-based directed graph generation to PostGreSQL
PHASE4: Initialize and Run Contraction by PostGreSQL
PHASE5: Build contraction based HighOrder2 graph
PHASE6: Build traversal clusters based HighOrder2 graph
PHASE7: Build Intra-cluster and Inter-cluster links
PHASE8: Build Waterway Geometries for Objective Rivers
PHASE9: Find Shortest Path
PHASE10: Map Publishing (QGIS)
PHASE11: Finalyze and Publish to Internet as AppDB
POST-PHASE12: Combining Two G2K projects
PHASE12: UNUSED: OPTIONAL: Initialize and Run HighOrder2 Contraction by PostGreSQL
PHASE13: UNUSED: OPTIONAL: Generate shortcut geometries using HighOrder2 contraction
Title: G2K Jal Sethu -- Bringing River Ganga to River Kaveri
Motivation: Indian subcontinent has one stark natural north-south differentiation: water is generally abundant in north and generally scarce in south. The negative consequence of water abundance is under utilization due to flooding; of water scarcity is under utilization due to drought. Leveling such abundance and scarcity could raise value utilization everywhere -- this could well be one of the great achievements of India.
For Indian civilization, the rivers of the land are the spiritual arteries. The Bhagiratha effort of bringing the river Ganga to all other rivers is the civilizational achievement of Indian peoples
Spiritual Motivation: For Indian civilization, the rivers of the land are the spiritual arteries. The travels of epic hero Rama is not delineated by regimes/dynasties that he travels through; but by the rivers and ponds that he crosses -- eventually culminating at crossing of the big-pond in Rameshwaram. Immersing in waters of the rivers is one of the commonest spiritual practices of the Indian peoples. Mythically, Bhagiratha took the synonymous effort to bring river Ganga to Himalayas. The comparable effort that Indian civilization would get self-motivated to achieve would be bringing the river Ganga to all other rivers
Objective: Finding cost-effective path to transport water (or any fluid) from any geographical location to any other location -- however far away they are. For this objective, G2K project delivers toolkit that could be used for planning cost-effective flow-pathways for very large distances.
Project Summary:
The natural terrain topography of valleys and ridges of different scales naturally define the pathways of flow of waters in different scales as brooks and creeks and tributaries and rivers. While the terrain topography enables natural flows to form natural pathways, it also defines the fundamental limiting constraint to the flow from a geographical location to any other arbitrary geographical location (water is not naturally going to flow from lower terrain to upper terrain). Superseding such natural flow through aqueducts or channels or transportation are essentially overcoming this fundamental constraint by some artificial implementations.
Historically, artificial flow pathways from a specific geographical point-location to another specific geographical point-location had been implemented by different civilizations in various times. However, such projects had specific scope in geographical locations and/or distances. The limited scope had helped the projects in different ways: complexity of the problem became specific and limited; the artificial pathways implemented need not have been the best-possible (cost-effective) one.
Modern satellite images, Big Data powers, and the computational techniques could enable us to build an analytical framework to overcome the scope limitations: complexity of very large problem-space could be tamed; exponentially large number of possible pathways could be analyzed to identify the cost-effective pathways
G2K project implements an analytical framework including interactive map that could aid finding the cost-effective flow pathways from any geographical location (or region) to any other location (or region) -- however far away the source location/region and the destination location/region are separated.
Implementation Summary:
The source data for G2K project are:
- Global Digital Elevation Model (DEM) for the area-of-interest in 10m resolution from ASTER3 satellites.
- Soil Classification Data (WRB 2006) in 250m resolution from UN SoilGrids.
G2K formulates a cost function based on the geographical elevation value in DEM to the fundamental cost to the flow across the two-dimensional grid of 10m resolution. The Soil Classification Data becomes cost-multiplier for each region – as the nature of the soil changes the cost of routing.
The two-dimensional grid of 10m resolution with costs associated forms a graph with each 10m region as node and all neighbor nodes (maximum 8) are linked by directed edges associated with value of the flow-cost.
When the terrain modeled as a massive graph, the problem of finding cost-effective paths from any geographical location to any another location gets reduced to solving graph shortest-path problem.
While shortest-path problem is a matured technical problem with multitude solutions, the biggest challenge of graphical terrain as graph is the size of the problem space.
Rough estimation of the problem size:
Let us suppose we are looking for shortest paths within 100km x 100km region.
Finding shortest path from any 10m location to any other 10m location in 100km x 100km region would mean:
Graph of ~100million nodes and ~800million directed edges
Memory representation of ~70GB for nodes and ~120GB for edge; ~250GB in total including support data structures
~2Billion computation of shortest-path algorithm such as Djkstra -- about 10 days of time for large computers
Extending the rough estimations for 100km x 100km region to entire Indian subcontinent would roughly mean multiplying the storage and runtime by 30x15 times.
Such problem that is massive in both time and space, could either be solved by super computers (vertically scaled solution) or by Big Data techniques (horizontally scaled solution)
G2K project implements Big Data techniques to break the problem into sequence of phases; each phases into parallel batches; each batches into concurrently running tasks
G2K project uses consumer/small-business commodity systems to solve the massive problem:
With two 6 core, 48 thread CPU; 128GB DDR2 RAM; 6TB NVME Disks, 100km x 100km problem gets solved and published in ~3days
Project Objectives and Algorithmic Choice:
As explained in problem size estimation, the Big Data techniques and well-known shortest path algorithms could solve finding cost-effective routes (shortest paths) between a single source point-location to another single or set of destination point-location(s) in few days.
However, the project would not be fruitful enough if it were to find cost-effective routes between few targeted source-to-destination point-locations (e-g., Ganga River near Prayagraj to Kaveri River near Mysuru)
Hence, the project took as objective to enable capabilities to find cost-effective routes between any source-to-destination point-locations.
After reviewing hundreds of advanced shortest-path algorithms, the project identified the Contraction Hierarchies Algorithm (see: https://en.wikipedia.org/wiki/Contraction_hierarchies) as the most appropriate algorithm for meeting the objective of G2K project
G2K Contraction Hierarchies Implementation
G2K uses Contraction Hierarchies Algorithm as the central mechanism to search and save ALL possible shortest paths from any point-location to any other point-location.
The Big Data techniques could break the problem into batches and micro-batches to be run horizontally. Aided by cache-localization for each micro-batch, the G2K project could tremendously reduce the exponential compute-time problem-space into log-linear one.
Once ALL possible shortest paths throughout the nation were searched and saved, G2K project ‘cluster’ them utilizing the path-intersections. Then, all these clusters are ensured to be reachable among them in such a way that more than 99.9% of entire nation could be reachable by hoping from cluster to cluster.
Project Outcomes:
- A final analytical graph model that could find cost-effective path from any node to any node within 30 seconds -- even when the nodes are geographically thousands of kilometers away
- Saved publication of three cost-effective paths each between one major river to another river:
- Ganga - to - Kaveri
- Ganga - to - Yamuna
- Yamuna - to - Narmadha
- Narmadha - to - Godhavari
- Godhavari - to - Krishna
- Krishna - to - Kaveri
- Sutlej- to - Yamuna
- Automated process to create and publish cost-effective paths between any regions
- Automated process to extract high-resolution path routing details (down to 10m resolution)
- Interactive Map, G2K Jal Sethu, (built with OpenStreetMap as background plane) to dynamically create water-way routings
PROD Lat/Lon Goal/Scope
PROD Goal:(11,75) - (26,81) and (27,77)-(27,79) 167=112-5-4 ~= 104 + (27,77) + (27,78) + (27,79) ~= 107
Goal:(11,75) - (26,82) 168=128-10-4=114
PROD Orig Goal:(10,74) - (27,79) 186=108-2=106
B2Y Goal: (29,74) - (32,77) = 9
N26E081-N11E075 (167 + 3=115 rect; -4 sea-surface = 111; -4 mostly sea-surface = 107 tiles * 12960000 = 1386720000 nodes (1.38B) DB Size: ~3.4T)
Orig: N29E079-N12E074 (18*6=108 tiles 1350969135 nodes (1.3B) DB Size: ~3.4T)
DEV Lat/Lon Goal/Scope: (28,77) - (30,81)
N29E080-N28E077 (24=8 tiles * 12960000 = 103680000 bides (103M) DB Size: ~245GB ~30.6GB/tile)
N29E079-N11E074 (196=114 tiles 1477440000 nodes (1.4B) DB Size: ~3.5T)
N29E079-N10E074 (20*6=120 tiles 1555200000 nodes (1.5B) DB Size: ~3.7T)
Haridwar/Binjor: N29E078
Ganga near Binjor (NH34): 29.300677, 78.100104 (29.3713/78.0392) (29.3424/78.0510)
https://www.openstreetmap.org/#map=11/29.3006/78.1001
Ganga south of Haridwar, east of Sultanpur: 29.7331, 78.1938
Kali Nadi near Meerut : 29.1589, 77.7549
https://www.openstreetmap.org/#map=11/29.1589/77.7549
Yamuna north of Delhi, near Baghpat 28.9999/77.2002
https://www.openstreetmap.org/#map=12/28.9999/77.2002
Area of interest:
PROD: Scope: (11,75) - (26,81) and (27,77)-(27,79)
B2Y Scope: (29,74) - (32,77) = 9
Ganga near Prayagraj: 25.3524, 81.91954
Ganga near Binjor (NH34): 29.3713, 78.0392
Ganga at Badaun: 27.9306, 78.8639
Ganga at Kannauj (West of Lucknow): 27.0246, 79.9776
Kaveri near Mettur: 12.15877, 77.74365
Kaveri north of Mysuru (Srirangpatna): 12.4264, 76.6411
Kaveri at Hogenakkal: 12.1203, 77.7766
Kaveri south of Gopinatham: 12.0263, 77.7034
Ravi near Ajnala: 31.9312, 74.7977
Beas near Sri Hargobindpur: 31.67966, 75.48811
Saharanpur/Muzaffarnagar: N29E077
Yamunanagar: N30E077
Yamuna south of Mathura: 27.3986, 77.7544
Srirangapatna: N12E076
Kaveri east of Srirangapatna: 12.3990, 76.7450
Kaveri at Bhavani, north of Erode: 11.4255, 77.6850
Kaveri at Trichy: 10.8994, 78.5419
Sample Screens:
1. Saved and Published paths between Godhavari River and Krishna River
2. G2K Jal-Sethu Interactive Path Exploration between Ganga River and Yamuna River (north of Delhi)
